In computer science and discrete mathematics, an inversion in a sequence of numbers is a pair of numbers in the sequence that are "out of order" with respect to an ascending or descending order.
Contents |
Formally, let be a sequence of n distinct numbers. If and , then the pair is called an inversion of .[1][2]
The inversion number of a sequence is one common measure of its sortedness.[3][2] Formally, the inversion number is defined to be the number of inversions, that is,
Other measures of (pre-)sortedness include the minimum number of elements that can be deleted from the sequence to yield a fully sorted sequence, the number and lengths of sorted "runs" within the sequence, and the smallest number of exchanges needed to sort the sequence.[4] Standard comparison sorting algorithms can be adapted to compute the inversion number in time O(n log n).
The inversion vector V(i) of the sequence is defined for i = 2, ..., n as . In other words each element is the number of elements preceding the element in the original sequence that are greater than it. Note that the inversion vector of a sequence has one less element than the sequence, because of course the number of preceding elements that are greater than the first is always zero. Each permutation of a sequence has a unique inversion vector and it is possible to construct any given permutation of a (fully sorted) sequence from that sequence and the permutation's inversion vector.[5]
The set of permutations on n items can be given the structure of a partial order, called the weak order of permutations, which forms a lattice.
To define this order, consider the items being permuted to be the integers from 1 to n, and let Inv(u) denote the set of inversions of a permutation u for the natural ordering on these items. That is, Inv(u) is the set of ordered pairs (i, j) such that 1 ≤ i < j ≤ n and u(i) > u(j). Then, in the weak order, we define u ≤ v whenever Inv(u) ⊆ Inv(v).
The edges of the Hasse diagram of the weak order are given by permutations u and v such that u < v and such that v is obtained from u by interchanging two consecutive values of u. These edges form a Cayley graph for the group of permutations that is isomorphic to the skeleton of a permutohedron.
The identity permutation is the minimum element of the weak order, and the permutation formed by reversing the identity is the maximum element.
The following files show the permutations of 4 elements, their inversion vectors and their sets of up to six inversions. When a pair (i,j) is marked in red as an element of the inversion set, it means that the elements on places i and j are out of their natural order in the permutation. For example the inversion set of permutation number 1 contains only the pair (1,2), so only the elements on places 1 and 2 are out of their natural order.
These are the six possible pairs.